补题进度:Done
我的人生也就做做水题维持维持生活了
pb−ds库是个神奇的东西啊
A,B
签到
C
很显然枚举每个删除的线段,取左端点的max,右端点的min比较一下就好了
D
题意
给n个数,每个数可以其他的数拼接一起(显然一共有n·(n−1)种搭配),问其中可以被 k 整除的方案数
题解
- 直接开是10个
map(__gnu_pbds::cc_hash_table),记录每个数作为前缀的情况 - 然后枚举每个数作为后缀的情况即可
代码
1 |
|
E
题意
给一颗n个节点的树,问最少添加几条边使得节点1到其他任何点的距离不超过2。
n≤2·105
BZOJ 1950 简化版
题解
- 很显然遇到不符合的不是最优的(比如:1-2-3-4-5-6,答案是1,想不到吧)。
- 对于所有不满足的点,假设我们现在在最底层,显然从1连它的父亲肯定可以解决它的问题修改掉它的距离,和它父亲的距离,dfs跑一次即可。
- 需要注意每次修改完一个点,从这个点出发其他的点也要修改。
- 怎么又被全局变量v坑了啊
代码
1 |
|
F
题意
给两种颜色分别有数量 a 和 b,现要求用a+b个颜色组成一个矩形(即矩形的面积为a+b),并且至少有一种颜色a或b可以自己形成矩形,问最小周长
题解
- 约数个数没有规律的分布,但好像都不太大的样子
- 所以可以枚举 a+b 的约数,暴力枚举a或b为矩阵的情况,判断a或b的两边是否小于等于当前a+b的约数即可
- 时间复杂度O(103·103)左右
约数个数
结论:打表可以看出[1,1e14]内的数的约数个数大概也就103级别。
约数没有规律分布
质数分布:nlogn
tokitsukaze代码
1 |
|